package demo4_sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) throws InterruptedException {
        int[] arr = new int[]{3, 5, 2, 7, 8, 1, 2, 0, 4, 7, 4, 3, 8};
        System.out.println(Arrays.toString(arr));
        shellSort1(arr);
        System.out.println(Arrays.toString(arr));
    }

    //希尔排序 交换法
    public static void shellSort(int[] arr) {
        //遍历所有的步长
        for (int d = arr.length / 2; d > 0; d /= 2) {
            //遍历所有元素
            for (int i = d; i < arr.length; i++) {
                //遍历本组中所有的元素
                for (int j = i - d; j >= 0; j -= d) {
                    //如果当前元素大于加上步长后的那个元素
                    if (arr[j] > arr[j + d]) {
                        int temp = arr[j];
                        arr[j] = arr[j + d];
                        arr[j + d] = temp;
                    }
                }
            }
        }
    }

    //希尔排序 位移法
    public static void shellSort1(int[] arr) throws InterruptedException {
        //遍历所有的步长
        for (int d = arr.length / 2; d > 0; d /= 2) {
            //根据步长遍历所有元素
            for (int i = d; i < arr.length; i += d) {
                //遍历本组中所有的元素
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - d]) {
                    while (j - d >= 0 && temp < arr[j - d]) {
                        //移动
                        arr[j] = arr[j - d];
                        j -= d;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;

                }
            }
        }
    }
}
